package chapter4_hash;

import sun.reflect.generics.tree.Tree;

import java.util.HashSet;
import java.util.TreeSet;

/**
 * 查找表和滑动窗口的配合 hash用于检查是否存在是适合的
 *      搜索
 * 有    二分/tree
 * 无    hash
 * 万里挑一根据值的话 首选hash
 */
public class ContainsValueInRange {

    static boolean containsValue(int[] nums, int k) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashSet.contains(nums[i])) {
                return true;
            }
            hashSet.add(nums[i]);
            if (hashSet.size() == k + 1) {
                hashSet.remove(nums[i - k]);
            }
        }
        return false;
    }

    static boolean containsValueII(int[] nums, int k, int v) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            //存在一个值，这个值比新来的值-v稍大 并且比 新来的值+v小
            if (treeSet.ceiling(nums[i] - v) != null
                    && treeSet.ceiling(nums[i] - v) <= nums[i] + v) {
                return true;
            }
            treeSet.add(nums[i]);
            if (treeSet.size() == k + 1) {
                treeSet.remove(nums[i - k]);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 2, 5, 6, 7};
        System.out.println(containsValue(arr, 2));
    }
}
